#!usr/bin/env python  
# -*- coding:utf-8 _*-
""" 
@author:robot
@file: binary_serach_tree.py 
@version:
@time: 2022/11/06 
"""


class BinarySearchTree:
    def __init__(self) -> None:
        self.tree = None

    class Node:
        def __init__(self, data)->None:
            self.data = data
            self.left = None
            self.right = None

    def insert(self, value):
        if self.tree is None:
            self.tree = self.Node(value)
            return

        p = self.tree
        while p is not None:
            if value > p.data:
                if p.right is None:
                    p.right = self.Node(value)
                    return
                p = p.right
            elif value < p.data:
                if p.left is None:
                    p.left =self.Node(value)
                    return
                p = p.left

    def find(self, value):
        p = self.tree
        while p is not None:
            if value > p.data:
                p = p.right
            elif value < p.data:
                p = p.left
            else:
                return p
        return None

    def delete(self, value):
        """
        情况一：要删除的节点没有子节点

        只需要直接将父节点中，指向要删除节点的指针置为 null。比如图中的删除节点 55。

        情况二：如果要删除的节点只有一个子节点（只有左子节点或者右子节点），

        只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。

        情况三：如果要删除的节点有两个子节点

        找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。
        然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18
        :param value:
        :return:
        """
        p = self.tree
        pp = None

        # 为空返回
        if p is None:
            return

        while p is not None and p.data != value:
            ## pp记录根节点
            pp = p
            # 在右侧寻找
            if value > p.data:
                p = p.right
            # 在左侧寻找
            elif value < p.data:
                p = p.left

        if p.left is not None and p.right is not None:
            tmp_p = p.right
            tmp_pp = p
            # 找要删除结点的右子树中的最小值
            while tmp_p.left is not None:
                tmp_pp = tmp_p
                tmp_p = tmp_p.left
            p.data = tmp_p.data
            p = tmp_p
            pp = tmp_pp

        if p.left is not None:
            child = p.left
        elif p.right is not None:
            child = p.right
        else:
            child = None

        # 删除根节点
        if pp is None:
            self.tree = child
        elif pp.left is p:
            pp.left = child
        elif pp.right is p:
            pp.right = child

    def pre_order(self, node):
        if node is None:
            return
        print(node.data)
        self.pre_order(node.left)
        self.pre_order(node.right)

    def in_order(self, node):
        if node is None:
            return
        self.in_order(node.left)
        print(node.data)
        self.in_order(node.right)

    def post_order(self, node):
        if node is None:
            return
        self.post_order(node.left)
        self.post_order(node.right)
        print(node.data)

def test_binary_search_tree():

    binary_search_tree = BinarySearchTree()
    data = [1, 10, 20, 40, 13]
    for i in data:
        binary_search_tree.insert(i)
    assert 20 == binary_search_tree.find(20).data
    binary_search_tree.in_order(binary_search_tree.tree)
    print("-----------------------")
    binary_search_tree.delete(20)
    assert binary_search_tree.find(20) is None
    # 1 10 40 13
    binary_search_tree.pre_order(binary_search_tree.tree)
    print("-----------------------")
    # 1 10 13 40
    binary_search_tree.in_order(binary_search_tree.tree)
    print("-----------------------")
    # 13 40 10 1
    binary_search_tree.post_order(binary_search_tree.tree)


if __name__ == '__main__':
    test_binary_search_tree()